The invention disclosed in the present application relates to a linear interpolator and a designing method thereof. More specifically, the present invention relates to a technique for calculating a linear interpolated value of two signed interpolation target values by a hardware circuit, and to a technique for realizing a simple hardware circuit which can calculate a high-accuracy linear interpolated value.
As a method for obtaining an intermediate value of two values by means of interpolation, linear interpolation is most representative. Recently, in particular, as a method for image processing, this linear interpolation is popularly utilized. For example, the method for image synthesis generally called “α-blend” is a method in which an image A and an image B are synthesized at a ratio of α:(1−α) (0≦α≦1), and processing for obtaining an intermediate value of a pixel value of the image A and a pixel value of the image B by means of linear interpolation is performed. Also when enlarging or reducing an image at an arbitrary magnification, linear interpolation is used.
The basic principle of linear interpolation is that calculation is performed for obtaining a linear interpolated value C expressed as C=(1−D)*A+D*B (* sign representing multiplication) based on two interpolation target values A and B and an interpolation rate D (a value corresponding to said α, 0≦D≦1). When performing arithmetic operations based on this expression by using a digital computing unit, A, B, C, and D are all handled as digital data, and normally, the interpolation rate D is expressed by a bit sequence having finite digits showing only a decimal part. In this case, the interpolation rate D is handled as a value satisfying “0≦D<1” which does not include 1. U.S. Pat. No. 5,113,362 discloses a configuration of a computing unit which performs such linear interpolation (α-blend operation) by pipeline processing, and U.S. Pat. No. 5,517,437 discloses a configuration of a computing unit which performs linear interpolation by processing based on parallel processing.
The computing units disclosed in the patent documents and other conventional general linear interpolators assume that the interpolation target values are positive values. Normally, since pixel values of individual pixels composing an image are expressed as positive values, as the “α-blend” processing for general images, linear interpolation based on two positive pixel values is sufficient, and calculation can be performed by the computing units disclosed in the patent documents. However, recently, various image processes are applied, and an opportunities to handle an image including negative pixel values are quite many in number. For example, when it is necessary to subtract a pixel value of an image B from a pixel value of an image A in some process, an image C obtained as a result of this subtraction may include pixels with negative pixel values. As a matter of course, the use of the linear interpolation is not limited to the image processing, so that there are many other events that linear interpolation considering both positive and negative values becomes necessary.
To meet this demand, there have been proposed some computing units which can execute linear interpolation for two signed interpolation target values. However, all the signed linear interpolators which are conventionally proposed employ complicated circuitries for realizing a function to handle signed digital data, and cannot perform efficient calculation.
The linear interpolators which are conventionally proposed hardly satisfy both of calculation accuracy and circuit simplicity, and either one must be sacrificed. For example, the above-mentioned linear interpolator disclosed in U.S. Pat. No. 5,517,437 is comparatively simple in circuitry, however, an approximate value is obtained as a result of calculation, and instead of the original interpolation rate α (0≦α≦1), handling using a value D (0≦D<1) that does not include 1 is performed, so that a result of calculation when α=1 cannot be correctly obtained. Therefore, to make it possible to correctly obtain a result of calculation when α=1, it is necessary that a comparator for monitoring whether an input value of the interpolation rate α is 1 is given and an extra circuit for outputting an input value B as it is, and the circuitry inevitably becomes complicated.
On the other hand, a method in which a highly accurate result of calculation is obtained by performing division is also proposed, however, the circuitry is still complicated.
Recently, an opportunity to synthesize many images has increased. Therefore, a linear interpolator which always obtains a high-accuracy result of calculation has been demanded. On the other hand, downsizing and cost reduction of a circuit are also demanded, so that a linear interpolator whose circuitry is made as simple as possible has been demanded.
The present application also discloses a technique relating to a linear interpolation device which performs not only the above-described linear interpolation but also more complicated interpolation. Particularly, a technique relating to an interpolation device which performs interpolation of pixels by cubic spline interpolation when scaling display is performed by enlarging or reducing an image has been disclosed.
When displaying a digital image, scaling of enlargement and reduction often becomes necessary. An image given as digital data is a two-dimensional pixel array including a plurality of pixels having predetermined pixel values arrayed at predetermined pitches, so that in the case of enlargement and reduction, new pixels must be obtained by interpolation. As an interpolation method conventionally used for this image enlargement and reduction scaling, nearest neighbor and bilinear interpolation are known.
The nearest neighbor is a method for selecting a nearest sample pixel, so that in the case of reduction, by using a kind of pixel skipping, an image does not become blurred in scaling display. To the contrary, in the case of enlargement, several neighbor identical images are continuously spread, and this results in a flat mosaic image display.
On the other hand, according to bilinear interpolation, linear interpolation is performed by using pixel values of sample pixels on both ends of an interpolation interval, so that pixel values become different from original pixel values in the case of reduction and may result in collapsed image display. To the contrary, in the case of enlargement, pixel values subjected to linear interpolation are filled, so that a blurred image may be displayed. Thus, nearest neighbor and bilinear interpolation are poor in interpolation accuracy, so that it is considered that these defects arise.
Therefore, as interpolation with improved accuracy, for example, a basic concept of cubic convolution is shown in Robert G. Keys, “Cubic Convolution Interpolation for Digital Images Processing” IEEE Trans. on ASSP-29, No. 6, December 1981, pp. 1153-1160. In image scaling display of a digital television, as a bicubic image interpolation calculation with more improved accuracy, bicubic convolution is used. For example, in a medical-use image, scale display with much higher accuracy is required. Therefore, to employ higher-accurate interpolation, bicubic spline interpolation is proposed. A basic concept of cubic spline interpolation that is the base of the bicubic spline interpolation is shown in Hsieh S. Hou and Harry C. Andrews, “Cubic Splines for Image Interpolation and Digital Filtering” IEEE Trans. on ASSP-26, No. 6, December 1978, pp. 508-517, and Michael Unser, “Splines A perfect Fit for Signal and Image processing” IEEE Signal Processing Magazine, November 1999, pp. 22-38.
In the above-described cubic convolution, by using pixel values of (horizontal 4)*(vertical 4)=16 sample pixels, vertical 4-pixel interpolation is performed after horizontal 4-pixel interpolation, and cubic interpolation is performed two times in total per one pixel to be obtained. Thus, in convolution, four cubic curves are used and these are smoothly connected at boundaries among these. In actuality, this unknown coefficients equation has not been completely solved, and 1 coefficient is left undetermined. Therefore, −1 and −½ is experimentally used as the undetermined coefficient value, and meaning and accuracy of the interpolation are ambiguous.
On the other hand, in cubic spline interpolation, four cubic curves are used similarly to the convolution in the interpolation interval, and this interpolation is different in meaning and composition of the expressions from the convolution because the cubic spline interpolation attempts to realize faithful approximation by blending these curves. The number of sample pixels to be used for interpolation is not necessarily four, and may be more than four. Namely, the number of weighing factors when blending four cubic curves called B-splines in the interpolation interval is four. Therefore, the cubic spline interpolation has approximation accuracy higher than that of the convolution, however, cubic interpolation equations are calculated through complicated processes. Particularly, a process for calculating respective cubic spline functions from pixel values of S in total of sample pixels (S≧4) to be referred for interpolation and a process for obtaining pixel values of interpolation points by setting positions of the interpolation points and performing bicubic spline interpolation, are extremely complicated, and at the present, in the case of image enlargement and reduction scaling display being performed, a device which performs practicable cubic spline interpolation suitable for commercial use has not been realized.